package com.immediatus.util;

import java.util.Comparator;
import java.util.List;

public class InsertionSorter<T> extends Sorter<T>{

    @Override
    public void sort(final T[] array_, final int start_, final int end_, final Comparator<T> comparator_){
        for (int i = start_ + 1; i < end_; i++){
            final T current = array_[i];
            T prev = array_[i - 1];
            if (comparator_.compare(current, prev) < 0){
                int j = i;
                do{
                    array_[j--] = prev;
                } while (j > start_ && comparator_.compare(current, prev = array_[j - 1]) < 0);
                array_[j] = current;
            }
        }
    }

    @Override
    public void sort(final List<T> list_, final int start_, final int end_, final Comparator<T> comparator_){
        for (int i = start_ + 1; i < end_; i++){
            final T current = list_.get(i);
            T prev = list_.get(i - 1);
            if (comparator_.compare(current, prev) < 0){
                int j = i;
                do{
                    list_.set(j--, prev);
                } while (j > start_ && comparator_.compare(current, prev = list_.get(j - 1)) < 0);
                list_.set(j, current);
            }
        }
    }
}